package org.example.sword2offer.medium;

/**
 * @author: lynn
 * @description: 找出B中不属于A的数、
 * @算法复杂度： for循环m次，while循环logn次（如果没有特别说明，log均以2为底），此算法的时间复杂度为O(mlogn)
 * @date: 2021/4/28 15:05
 * @version 1.0.0
 *  
 */
public class FindBNotInA {
    public static void main(String[] args) {
        int[] A={2,5,7,8,9};
        int[] B={1,4,2,6,5,7};
        for (int i = 0; i <B.length ; i++) {
            int l=0;
            int r=A.length-1;
            int mid=l+(r-l)/2;
            int temp=B[i];
            while (l<r&& temp!=A[mid]){  //fixme  l<r&& temp!=mid
                if (temp>A[mid]){        //fixme  temp> mid
                    l=mid+1;             //fixme l=mid
                }else {
                    r=mid-1;             //fixme r=mid
                }
                mid=l+(r-l)/2;
            }
            if (A[mid] != temp) {
                System.out.println("B not in A: "+temp);
            }
        }
    }
}
